package leetcode

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

type ListNode struct {
	Val  int
	Next *ListNode
}

//输入：l1 = [2,4,3], l2 = [5,6,4]
//输出：[7,0,8]
//解释：342 + 465 = 807.
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	// 这里是头结点
	dummy := new(ListNode)
	// 当前指针位置
	cur := dummy
	// 进位缓存
	carry := 0

	for l1 != nil || l2 != nil || carry > 0 {
		cur.Next = new(ListNode)
		cur = cur.Next
		if l1 != nil {
			carry += l1.Val
			l1 = l1.Next
		}
		if l2 != nil {
			carry += l2.Val
			l1 = l2.Next
		}
		cur.Val = carry % 10
		carry /= 10
	}
	return dummy.Next
}

// 寻找两个正序数组的中位数
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	if len(nums1) > len(nums2) {
		return findMedianSortedArrays(nums2, nums1)
	}
	low, high, k, nums1Mid, nums2Mid := 0, len(nums1), (len(nums1)+len(nums2)+1)>>1, 0, 0
	for low <= high {
		nums1Mid = low + (high-low)>>1
		nums2Mid = k - nums1Mid
		if nums1Mid > 0 && nums1[nums1Mid-1] > nums2[nums2Mid] {
			high = nums1Mid - 1
		} else if nums1Mid != len(nums1) && nums1[nums1Mid] < nums2[nums2Mid-1] {
			low = nums1Mid + 1
		} else {
			break
		}
	}
	midLeft, midRight := 0, 0
	if nums1Mid == 0 {
		midLeft = nums2[nums2Mid-1]
	} else if nums2Mid == 0 {
		midLeft = nums1[nums1Mid-1]
	} else {
		midLeft = maxInt(nums1[nums1Mid-1], nums2[nums2Mid-1])
	}
	if (len(nums1)+len(nums2))&1 == 1 {
		return float64(midLeft)
	}
	if nums1Mid == len(nums1) {
		midRight = nums2[nums2Mid]
	} else if nums2Mid == len(nums2) {
		midRight = nums1[nums1Mid]
	} else {
		midRight = minInt(nums1[nums1Mid], nums2[nums2Mid])
	}
	return float64(midLeft+midRight) / 2
}

func maxInt(x, y int) int {
	if x > y {
		return x
	}
	return y
}
func minInt(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func threeSum(nums []int) [][]int {
	res := [][]int{}
	counter := map[int]int{}
	for _, value := range nums {
		counter[value]++
	}
	return res
}

// k[...]

func decodeString(s string) string {
	alphaStack := make([]byte, 0)
	countStack := make([]int, 0)
	alphaIndex := make([]int, 0)
	var count int
	for i := 0; i < len(s); i++ {
		if s[i] >= '0' && s[i] <= '9' {
			count = count*10 + int(s[i]-'0')
		} else if s[i] == '[' { // [ 后面肯定是字母
			// 可以把当前的数字放入次数数组
			countStack = append(countStack, count)
			count = 0

			alphaIndex = append(alphaIndex, len(alphaStack))
		} else if s[i] == ']' { // 对当前字母段出站
			// 获取当前字母段的次数 然后次数出栈
			c := countStack[len(countStack)-1]
			countStack = countStack[:len(countStack)-1]

			// 获取当前字母段开始的索引 然后索引出栈
			index := alphaIndex[len(alphaIndex)-1]
			alphaIndex = alphaIndex[:len(alphaIndex)-1]

			//获取当前的字母段
			str := string(alphaStack[index:])
			// 字母数组出站
			alphaStack = alphaStack[:index]

			for j := 0; j < c; j++ {
				alphaStack = append(alphaStack, []byte(str)...)
			}
		} else {
			alphaStack = append(alphaStack, s[i])
		}
	}
	return string(alphaStack)
}

type BitMap struct {
	bits []byte
	max  int
}

//初始化一个BitMap
//一个byte有8位,可代表8个数字,取余后加1为存放最大数所需的容量
func NewBitMap(max int) *BitMap {
	bits := make([]byte, (max>>3)+1)
	return &BitMap{bits: bits, max: max}
}

//添加一个数字到位图
//计算添加数字在数组中的索引index,一个索引可以存放8个数字
//计算存放到索引下的第几个位置,一共0-7个位置
//原索引下的内容与1左移到指定位置后做或运算
func (b *BitMap) Add(num uint) {
	index := num >> 3
	pos := num & 0x07 // 0111
	b.bits[index] |= 1 << pos
}

//判断一个数字是否在位图
//找到数字所在的位置,然后做与运算
func (b *BitMap) IsExist(num uint) bool {
	index := num >> 3
	pos := num & 0x07
	return b.bits[index]&(1<<pos) != 0
}

//删除一个数字在位图
//找到数字所在的位置取反,然后与索引下的数字做与运算
func (b *BitMap) Remove(num uint) {
	index := num >> 3
	pos := num & 0x07
	b.bits[index] = b.bits[index] & ^(1 << pos)
}

// 位图的最大数字
func (b *BitMap) Max() int {
	return b.max
}
